#include <iostream>
#include <memory>
#include "binary_tree.h"
#include "binary_search_tree.h"

using SharedPtrIntBinaryTree = BinaryTree<int, std::shared_ptr>;

int main(int , char* [])
{
    std::cout << "BST structure(before):\n"
            << "     5\n"
            << "   3   6\n"
            << "  2 4   7\n"
            << " 1\n";

    int five = 5;
    int nine = 9;

    SharedPtrIntBinaryTree::Pointer root(new SharedPtrIntBinaryTree(five));
    root->left.reset(new SharedPtrIntBinaryTree(3));
    root->left->left.reset(new SharedPtrIntBinaryTree(2));
    root->left->left->left.reset(new SharedPtrIntBinaryTree(1));
    root->left->right.reset(new SharedPtrIntBinaryTree(4));
    root->right.reset(new SharedPtrIntBinaryTree(6));
    root->right->right.reset(new SharedPtrIntBinaryTree(7));

    BinarySearchTree<SharedPtrIntBinaryTree> bst(root);
    std::cout << "Insert 9 " << (bst.insert(nine).second ? "success." : "failed.") << std::endl;
    std::cout << "Insert 9 " << (bst.insert(9).second ? "success." : "failed.") << std::endl;

    std::cout << "Remove 7 " << (bst.remove(7) ? "success." : "failed.") << std::endl;
    std::cout << "Remove 2 " << (bst.remove(2) ? "success." : "failed.") << std::endl;


    for(SharedPtrIntBinaryTree::Value value = 0; value < 10; ++value) {
        std::cout << "Search value " << value << " :";
        
        if(auto subTree = bst.find(value)) {
            std::cout << "Find! left: ";
            
            if(subTree->left) std::cout << subTree->left->value; 
            else std::cout << "null";

            std::cout << ", right: ";

            if(subTree->right) std::cout << subTree->right->value; 
            else std::cout << "null";

            std::cout << std::endl;
        }
        else {
            std::cout << "Could not found." << std::endl;
        }
    }


    
    return 0;
}
